#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
const int MAXN=1e5+10;
LL n,k,a[MAXN],tot,sum[MAXN],f[MAXN],g[MAXN],q[MAXN];
db slope(LL x,LL y)
{
	return (f[x]-sum[x]*sum[x]-(f[y]-sum[y]*sum[y]))*1.0/(sum[y]-sum[x]);
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(LL i=1;i<=n;++i)
	{
		scanf("%lld",&a[++tot]);
		if(!a[tot])--tot;
	}
	n=tot;
	for(LL i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
	for(LL i=1;i<=k;++i)
	{
		LL l=0,r=0;
		memset(q,0,sizeof(q));
		for(LL j=1;j<=n;++j)
		{
			while(l<r&&slope(q[l],q[l+1])<sum[j])++l;
			LL t=q[l];
			g[j]=f[t]+sum[t]*(sum[j]-sum[t]);
			while(l<r&&slope(q[r-1],q[r])>=slope(q[r],j))--r;
			q[++r]=j;
		}
		memcpy(f,g,sizeof(g));
	}
	printf("%lld\n",f[n]);
	return 0;
}
